1. Field of the Invention
The invention relates generally to processing data packets, and more specifically to the high speed filtering and/or classification of data packets.
2. Background Information
In a communications network, there is a well-recognized need to classify information units, such as data packets, that are passed between various intermediate nodes in the network, e.g., routers and switches, in order to support a wide range of applications, such as security control, packet filtering, Class of Service (CoS) and Quality of Service (QoS). Often, these intermediate nodes use access control lists (ACLs) to, inter alia, classify packets for these applications. An ACL typically comprises an ordered list of access control entries (ACEs), i.e., rules, where each rule defines a pattern (criterion) that is compared with data packets to be classified. The pattern may specify a source address, a destination address, a protocol or some other entity that is searched for in the data packet. For example, the pattern might be defined to search for a specific protocol in a data packet's header such as, the Transmission Control Protocol (TCP) or the Internet Protocol (IP). The pattern is used to determine if the rule applies to the data packet. If the pattern is found in the data packet, the rule is said to apply to the packet. As used herein, a packet header is that portion of a data packet that is used to classify the packet.
Associated with each rule is an action that specifies an act to be taken if the rule applies. In its simplest form, this action may be to “permit” the matched data packet to proceed towards its destination or to “deny” the packet from proceeding any further. In a more sophisticated form, complex policies and filtering rules may be implemented in the ACL to determine the course of the data packet. Conversely, if there is no match to any of the ACL's rules, the action may be to drop the data packet, i.e., “a final deny.”
Typically, a data packet is classified by searching for the first rule in the ACL that applies to the packet and performing the action associated with the rule. The number of rules involved and the amount of processing time needed to make this determination often depends on the approach taken. For example, one approach would be to run through the list of rules starting from the first rule in the list to the last rule in the list until a matching rule, i.e., a rule that applies to the data packet, is found. This approach is simple, but is not very efficient. For example, the time spent processing each data packet may vary as packets that meet the criteria associated with rules earlier in the list will be processed faster than packets that meet criteria associated with rules that are positioned farther down the list.
One approach to obtaining an overall faster processing of packets is to predetermine how often each rule is matched and place the most matched rules at the top of the list. However, this method is highly dependent on the packet mix and is not very flexible.
Another approach implements a technique whereby packets are classified using a predetermined number of lookup operations, such as described in U.S. patent application Ser. No. 09/557,480, now issued as U.S. Pat. No. 6,970,462, titled, “A Method for High Speed Packet Classification” filed on Apr. 24, 2000, by Andrew McRae and hereinafter referred to as the “'480 application.” This technique involves dividing a packet's header into sections and applying the sections to a fixed hierarchy of lookup tables to determine an outcome such as, e.g., a first matching rule that applies to the packet. The lookup tables are associated with equivalence sets that represent all possible combinations of matching rules for all values of the packet header sections. The sections of the packet are applied to a first level of lookup tables in the lookup table hierarchy to select entries in the first level tables that are associated with the packet. The contents of the selected entries are, in turn, applied to a second level of tables to select entries whose contents are applied to a third level and so on. Eventually, an entry in a final level table is selected and the matching rule associated with the packet is determined from the results of the selected entry final table entry.
The technique described in the '480 application assumes the lookup tables exist before a packet is classified. Computing resources, such as processor time and memory, needed to generate these lookup tables depends in part on the number of rules in the ACL. Generally, as the number of rules in the ACL increases, the computing resources needed to build and hold the lookup tables also increases. In systems having limited computing resources, the number of rules that can be supported by this technique may be limited.
A technique similar to the '480 application that utilizes system resources more efficiently is described in U.S. patent application Ser. No. 10/170,896, now issued as U.S. Pat. No. 7,236,493, titled, “Incremental Compilation for Classification and Filtering Rules” filed on Jun. 13, 2002 and hereinafter referred to as the “'896 application.” Like the '480 application, the '896 application employs a packet classifying technique that that uses a fixed hierarchical arrangement of lookup tables containing a first level and a series of successive levels to classify packets in a fixed number of lookup operations. The first level lookup tables are pre-generated. The successive level lookup tables are generated on a demand basis, i.e., when needed to classify a packet. The technique conserves valuable intermediate node resources, such as memory and computing resources, as table entries are calculated when needed meaning unlike the technique described in the '480 application where table entries calculated whether they are actually used or not.
One problem with the above-described techniques is that they require lookup operations at all levels of tables in the lookup table hierarchy before the packet is classified. In some cases, lookup operations performed to access information contained in the tables at successive levels in the hierarchy may be unnecessary as an action associated with classifying a data packet may have been determined by information accessed from prior lookup operations. For example, if a lookup table hierarchy contains four lookup tables, four lookup operations must be performed before an action associated with classifying a packet is known and can be performed. If after the second lookup operation enough information is acquired to determine the action, the remaining two lookup operations are still performed, even though they do not affect the action taken to classify the packet. Execution of these latter, unnecessary lookup operations wastes valuable resources and the present invention is directed to a technique that reduces such unnecessary operations.